/**
 * 279. Perfect Squares 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */
class PerfectSquares {
    /**
     * 方法： 使用动态规划求解完全平方数问题
     *       f[i]表示和为i的完全平方数的最少数量
     *       状态转移方程：f[i] = min(f[i-j*j]) + 1
     *       其中j是小于等于i平方根的正整数
     *
     * Args:
     *      n: int - 需要分解为完全平方数之和的正整数
     *
     * Returns:
     *      int: 和为n的完全平方数的最少数量
     *
     * Time: O(n * sqrt(n)) - 外层循环遍历到n，内层循环遍历到sqrt(n)
     *
     * Space: O(n) - 需要一个长度为n的数组存储动态规划状态
     */
    public int numSquares(int n) {
        int[] f = new int[n+1];
        for(int i = 1; i<= n; i++){
            int minx = Integer.MAX_VALUE;
            for(int j = 1; j * j <= i; j++){
                minx = Math.min(minx, f[i - j * j]);
            }
            f[i] = minx + 1;
        }
        return f[n];
    }
}